//有两种特殊字符： 
//
// 
// 第一种字符可以用一个比特 0 来表示 
// 第二种字符可以用两个比特(10 或 11)来表示、 
// 
//
// 给定一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一位字符，则返回 true 。 
//
// 
//
// 示例 1: 
//
// 
//输入: bits = [1, 0, 0]
//输出: true
//解释: 唯一的编码方式是一个两比特字符和一个一比特字符。
//所以最后一个字符是一比特字符。
// 
//
// 示例 2: 
//
// 
//输入: bits = [1, 1, 1, 0]
//输出: false
//解释: 唯一的编码方式是两比特字符和两比特字符。
//所以最后一个字符不是一比特字符。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= bits.length <= 1000 
// bits[i] == 0 or 1 
// 
// Related Topics 数组 
// 👍 244 👎 0

package com.cute.leetcode.editor.cn;


import java.util.HashSet;
import java.util.Set;

public class OneBitAnd2BitCharacters {
    public static void main(String[] args) {
        int[] nums = {1,1,4,1,2,4,11,5};
        new OneBitAnd2BitCharacters().new Solution().isOneBitCharacter2(nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 看最后的0能不能单独使用
         * 输入保证末尾是0
         * 如果前一位是1的话，本位一定被占用，进行标记，下一位判断时直接跳过并恢复标记
         */
        public boolean isOneBitCharacter(int[] bits) {
            if (bits.length == 1) return bits[0] == 0;
            boolean flag = false;
            for (int i = 1; i < bits.length ; i++) {
                if (flag) flag = false;// 前一位被占用了，恢复占用状态
                else if (bits[i - 1] == 1) flag = true;// 本位被占用了，进行标记
            }
            return !flag;// 返回最后有没有被占用即可
        }

        /**
         * 没病走两步的题解
         * 遇到1走两步，遇到0走一步，判断最后是否恰好走到末尾0
         */
        public boolean isOneBitCharacter2(int[] bits) {
            int len = bits.length;
            int index = 0;
            while (index < len - 1){
                index += bits[index] == 1 ? 2 : 1;
            }
            return index == len - 1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}